struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    while (cur) {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast = head, * lod = head;
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        lod = lod->next;
    }
    return lod;
}
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
    // write code here
    if (pListHead == NULL || pListHead->next == NULL) {
        return NULL;
    }
    struct ListNode* fast = pListHead, * lod = pListHead;
    while (k--) {
        if (fast == NULL) {
            return NULL;
        }
        fast = fast->next;
    }

    while (fast) {
        fast = fast->next;
        lod = lod->next;
    }
    return lod;
}
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL) {
        return list2;
    }
    if (list2 == NULL) {
        return list1;
    }
    struct ListNode* newHead = NULL;
    struct ListNode* cur = newHead;

    while (list1 && list2) {
        if (list1->val > list2->val) {
            if (cur == NULL) {
                cur = newHead = list2;
            }
            else {
                cur->next = list2;
                cur = cur->next;
            }
            list2 = list2->next;
        }
        else {
            if (cur == NULL) {
                cur = newHead = list1;
            }
            else {
                cur->next = list1;
                cur = cur->next;
            }
            list1 = list1->next;
        }
    }
    if (list1) {
        while (list1) {
            cur->next = list1;
            list1 = list1->next;
            cur = cur->next;
        }
    }
    else {
        while (list2) {
            cur->next = list2;
            list2 = list2->next;
            cur = cur->next;
        }
    }
    return newHead;
}
struct ListNode* removeElements(struct ListNode* head, int val) {
    if (head == NULL) {
        return head;
    }
    struct ListNode* newHead;
    newHead = (struct ListNode**)malloc(sizeof(struct ListNode));
    newHead->next = head;
    struct ListNode* cur = newHead;
    while (cur->next) {
        if (cur->next->val == val) {
            struct ListNode* next = cur->next;
            cur->next = cur->next->next;
            free(next);
        }
        else {
            cur = cur->next;
        }
    }
    return newHead->next;
}